Wireless communication systems often suffer from burst errors which occur in data transmitted over wireless channels. Interleaving and deinterleaving of data is a key technology for reducing influence of the burst errors. Wireless communication systems require interleavers for effective error correction. One of the interleavers is a bit interleaver which permutes bits stored in a memory at different addresses. The addresses are based on interleave patterns that vary among different wireless communication standards or specifications. Therefore, address generation for an interleaver targeting different wireless communication standards requires a flexible address generator. In wireless communications, an address generator needs to consecutively generate a large number of complicated addresses based on an interleave pattern.
In related arts of the present invention, a flexible address generator which generates such complicated addresses based on any interleave pattern is realized using a typical processor such as a CPU (Central Processing Unit) or a microprocessor. Such a processor may be implemented by software run on a CPU. A typical processor provides flexibility in generation of complicated addresses at the cost of low throughput. Each of the complicated addresses is generated using a sequence of ordinary instructions because no single-cycle instruction is available for address generation in a typical processor. The sequence is executed using multiple instruction cycles. Further, the number of instruction cycles for generating one address varies for each address to be generated. These reduce throughput of the address generator implemented with a typical processor.
Note that a deinterleaver for data which has been interleaved with a certain interleave pattern can be realized using an interleaver with an interleave pattern which is the inverse of the certain interleave pattern. Therefore, an interleaver with a flexible address generator functions as a deinterleaver for data interleaved by various interleave patterns.
Various types of interleavers and address generators are proposed in related arts of the present invention.
WO03/058823 discloses an interleaving apparatus with a flexible address generator which generates addresses for the various interleaver sizes thorough a single algorithm. However, this address generator is implemented by a typical processor or CPU and suffers low throughput.
EP-1850486-A1 discloses a parallel interleaver in which multiple interleaver circuits are arranged in parallel in order to realize high-speed, low-delay interleave processing. The parallel interleaver is capable of flexibly coping with modification of an interleave pattern. However, the circuitry of the parallel interleaver is very large and the address generator used therein has also a complicated arrangement.
U.S. Pat. No. 7,343,530-B2 discloses an address generator based on a SIMD (single-instruction and multiple-data) processor. The address generator generates multiple addresses in parallel to reduce number of address generation cycles. However, customized address generation instructions is required to generate one address every cycle. Due to limited instruction opcodes (operation codes) for customized instructions, it is not practical to provide customized instructions required by all interleave patterns. Therefore, U.S. Pat. No. 7,343,530-B2 does not teach a high throughput interleaver that is flexible for all interleave patterns.
U.S. Pat. No. 6,574,766-B2 discloses an interleaving-deinterleaving apparatus with a customized address generator which reduces the number of cycles for address generation. Each customized address generator includes a counter and a look-up table to which the output of the counter is supplied. A memory can function as an interleaver and a deinterleaver depending on the selection of outputs of the customized address generator. Due to limited flexibility of the customized address generator, U.S. Pat. No. 6,574,766-B2 does not teach a high throughput interleaver that is flexible for all interleave patterns.
JP-7-254862-A discloses an interleaving-deinterleaving circuit which copes with a plurality of interleave formats. The circuit includes: a memory, a plurality of counters, a multiplexer generating a memory address by combining the outputs of counters, and a mode controller initializing the counters to values corresponding the selected interleave format when the counters deliver ripple-carry signals. However, since the address is generated based on the counted values, the interleaver is not flexible for all arbitrary interleave patterns.
WO2005/091509 discloses a multiple-processor-based address generator which generates an address value for addressing an interleaver memory, wherein consecutive address fragments to which an MSB (Most Significant Bit) is to be appended are generated. In the address generator, only a fraction of the address fragments generated, which potentially will exceed a maximum allowable value, is compared with the maximum allowable value.
FIG. 1 illustrates the address generator of WO2005/091509. This address generator 800 includes: a predetermined number of registers 810a to 810d; multiplexer 820a to 820d connected to the inputs of registers 810a to 810d, respectively; first permutation unit 830a supplied with the outputs of registers 810a to 810d; first address fragment calculation unit 840a supplied with the outputs of registers 810a to 810d; second permutation unit 830b supplied with the multiple outputs of first address fragment calculation unit 840a; second address fragment calculation unit 840b supplied with the multiple outputs of first address fragment calculation unit 840a; arbiter (or selector) 850 selecting one of outputs of first and second permutation units 830a and 830b; comparator 860 supplying control signals E and M to registers 810a to 810d and arbiter 850, respectively; and a toggle unit 870 adapted to concatenate or append one of several MSBs to the output of arbiter 850.
FIG. 2 illustrates the operation of the address generator shown in FIG. 1. First, the procedure is initialized in step 900, then the odd address fragment is loaded into the registers at step 901, the next and second next address fragments are generated at step 902, and the odd and next address fragments are permuted at step 903. After the permutation, it is judged whether the odd permuted address fragment is within range in step 904. If yes, the MSB is appended to the odd permutated address fragment in step 905, the present values of the registers are withheld in step 906, the generated address value is outputted in step 907, and then the procedure proceeds to step 908. If no in step 904, the procedure directly proceeds to step 908.
In step 908, the MSB is appended to the next permuted address fragment, and then the next address value is outputted in step 909. In step 910, it is determined whether all possible address values have been generated or not. If not, the procedure returns to step 901. Otherwise, the procedure is ended.
The address generator of WO2005/091509 is characterized in that it includes two permutation units 830a and 830b and arbiter 850. The output of first permutation unit 830a is an odd address fragment denoted as Aodd while the output of second permutation unit 830b is an even address fragment denoted as Aeven. If Aodd is within a desired range, as shown in step 904 of FIG. 2, arbiter 850 selects Aodd as the current output. Then arbiter 850 selects Aeven as the next output. This means in the current cycle, if Aodd is not ready but Aeven is ready, arbiter 850 cannot select Aeven as the output of the current cycle. As a result, there is no output in the current cycle and throughput of the address generator is reduced. In other words, wait cycles are necessary if address from permutation 830a or permutation unit 830b is not ready. Therefore, WO2005/091509 does not teach a high throughput interleaver that is flexible for all interleave patterns.